package leetcode;
import java.util.*;
/**
 * 17.电话号码的字母组合
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 输入：digits = ""
 * 输出：[]
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 */
public class Num_17 {
    List<String> outter = new ArrayList<>();
    List<Character> inner = new ArrayList<>();
    char[][] chars = {{'.','.','.','.'}, {'.','.','.','.'}, {'a','b','c','.'}, {'d','e','f','.'},
                                         {'g','h','i','.'}, {'j','k','l','.'}, {'m','n','o','.'},
                                         {'p','q','r','s'}, {'t','u','v','.'}, {'w','x','y','z'}};

    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return outter;
        }
        dfs(digits,0);
        return outter;
    }
    
    private void dfs(String digits, int startIndex) {
        //边界条件
        if(inner.size() == digits.length()){
            String str = toString(inner);
            outter.add(str);
            return;
        }
        // num为字符对应的数字 [2,9]
        char c = digits.charAt(startIndex);
        int num = c - '0';
        int end = (num==7 || num==9) ? 4 : 3;
        for (int i = 0; i < end; i++) {
            inner.add(chars[num][i]);
            dfs(digits, startIndex + 1);
            inner.remove(inner.size() - 1);
        }
    }
    
    //将字符数组转化为字符串
    private String toString(List<Character> list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }
}
